package com.atwy.sort;

/**
 * 冒泡排序：
 * 1.比较相邻的元素。如果第一个比第二个大，就交换它们两个；
 * 2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
 * 3.针对所有的元素重复以上的步骤，除了最后一个；
 * 4.重复步骤1~3，直到排序完成。
 *
 * 优化：
 * 1、设flag，在某一趟遍历后flag没有变化说明已经排好序
 * 2、第一次冒泡后，有一个数（最大数）已经在位了，第i次冒泡后，有i个数已经排好序在位置上了，
 * 所以冒泡比较时不需要比较 n次
 */
public class BubbleSorting {
    public static void main(String[] args) {
        int[] array = {3, 65, 2, 34, 12, 5, 9};
        sort(array);
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + "\t");
        }
        System.out.println();
        System.out.println("=============");

        int max = 80000;
        int arry[] = new int[max];
        for (int i = 0; i < max; i++) {
            arry[i] = (int)(Math.random()*8000000);
        }
        long start = System.currentTimeMillis();
        System.out.println("排序开始:"+start);
        sort(arry);
        long end = System.currentTimeMillis();
        System.out.println("排序结束:"+end);
        System.out.println("总耗时"+(end-start));
    }

    public static void sort(int[] array) {
        int max = 0;
        for (int i = 1; i <= array.length; i++) {
            // 第一遍冒出最大的那个数
            // 最多 n遍就能排好序
            for (int j = 0; j < array.length - 1; j++) {
                if (array[j] > array[j + 1]) {
                    max = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = max;
                }
            }

        }
    }

    /**
     * 优化
     * @param array
     */
    public static void sort2(int[] array) {
        int max;
        boolean flag ;
        for (int i = 1; i <= array.length; i++) {
            flag = false;
            // 第一遍冒出最大的那个数
            // 每次冒泡只需遍历 n-i 次即可
            for (int j = 0; j < array.length - i; j++) {
                if (array[j] > array[j + 1]) {
                    max = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = max;
                    flag = true;// 发生了交换
                }
            }
            if(!flag){
                break;
            }

        }
    }



}
